home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_11_12 / allison / bitstr.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-10  |  8.3 KB  |  448 lines
  1. LISTING 5 - Bitstring Class Implementation
  2. // bitstr.cpp
  3.  
  4. #include <assert.h>
  5. #include <iostream.h>
  6. #include <string.h>
  7. #include "string.hpp"
  8. #include "bitstr.h"
  9.  
  10. // Public Functions:
  11. bitstring::bitstring(unsigned long val, size_t n)
  12. {
  13.     assert(n < NPOS);
  14.  
  15.     // val == 0 is easy...
  16.     if (val == 0)
  17.     {
  18.         init(n);
  19.         return;
  20.     }
  21.  
  22.     // Find highest significant bit
  23.     unsigned long temp = val;
  24.     int high_bit = 0;
  25.     for (int i = 0; temp; ++i)
  26.     {
  27.         if (temp & 1)
  28.             high_bit = i;
  29.         temp >>= 1;
  30.     }
  31.  
  32.     // Determine nbits_ and construct
  33.     nbits_ = high_bit + 1;
  34.     if (nbits_ < n)
  35.         nbits_ = n;
  36.     init(nbits_);
  37.  
  38.     // Store bit pattern
  39.     for (i = 0; i < nbits_; ++i)
  40.     {
  41.         if (val & 1)
  42.             set_(i);
  43.         val >>= 1;
  44.     }
  45. }
  46.  
  47. bitstring::bitstring(const string& s)
  48. {
  49.     // Validate that s has only 0's and 1's
  50.     for (int i = 0; i < s.length(); ++i)
  51.     {
  52.         char c = s.get_at(i);
  53.         if (c != '0' &&  c != '1')
  54.             break;
  55.     }
  56.     assert(i == s.length());
  57.  
  58.     from_string(s);
  59. }
  60.  
  61. bitstring::bitstring(const bitstring& b)
  62. {
  63.     init(b.nbits_);
  64.     memcpy(bits_,b.bits_,nblks_ * sizeof bits_[0]);
  65. }
  66.  
  67. string bitstring::to_string() const
  68. {
  69.     char *s = new char[nbits_+1];
  70.     for (int i = 0; i < nbits_; ++i)
  71.         s[i] = '0' + test_(i);
  72.     s[nbits_] = '\0';
  73.     string s2(s);
  74.     delete [] s;
  75.     return s2;
  76. }
  77.  
  78. bitstring& bitstring::operator=(const bitstring& b)
  79. {
  80.     if (this != &b)
  81.     {
  82.         delete [] bits_;
  83.         init(b.nbits_);
  84.         memcpy(bits_,b.bits_,nblks_ * sizeof bits_[0]);
  85.     }
  86.     return *this;
  87. }
  88.  
  89. int bitstring::operator==(const bitstring& b) const
  90. {
  91.     return (nbits_ == b.nbits_) &&
  92.       !memcmp(bits_,b.bits_,nblks_ * sizeof bits_[0]);
  93. }
  94.  
  95. bitstring& bitstring::set()
  96. {
  97.     memset(bits_,~0u,nblks_ * sizeof bits_[0]);
  98.     cleanup();
  99.     return *this;
  100. }
  101.  
  102. bitstring& bitstring::set(size_t pos, int val)
  103. {
  104.     assert(pos <= nbits_);
  105.     if (pos == nbits_)
  106.         length(nbits_ + 1); // Append
  107.  
  108.     set_(pos,val);
  109.     return *this;
  110. }
  111.  
  112. bitstring& bitstring::reset(size_t pos)
  113. {
  114.     assert(pos <= nbits_);
  115.     if (pos == nbits_)
  116.         length(nbits_ + 1); // Append
  117.  
  118.     reset_(pos);
  119.     return *this;
  120. }
  121.  
  122. bitstring& bitstring::reset()
  123. {
  124.     memset(bits_,0,nblks_ * sizeof bits_[0]);
  125.     return *this;
  126. }
  127.  
  128. bitstring& bitstring::toggle()
  129. {
  130.     size_t nw = nblks_;
  131.     while (nw--)
  132.         bits_[nw] = ~bits_[nw];
  133.     cleanup();
  134.     return *this;
  135. }
  136.  
  137. int bitstring::any() const
  138. {
  139.     for (int i = 0; i < nblks_; ++i)
  140.         if (bits_[i])
  141.             return 1;
  142.     return 0;
  143. }
  144.  
  145. size_t bitstring::count() const
  146. {
  147.     size_t sum = 0;
  148.     for (int i = 0; i < nbits_; ++i)
  149.         if (test_(i))
  150.             ++sum;
  151.     return sum;
  152. }
  153.  
  154. bitstring& bitstring::operator&=(const bitstring& b)
  155. {
  156.     bitstring rhs(b);
  157.  
  158.     equalize(rhs);
  159.     for (int i = 0; i < nblks_; ++i)
  160.         bits_[i] &= rhs.bits_[i];
  161.     return *this;
  162. }
  163.  
  164. bitstring& bitstring::operator|=(const bitstring& b)
  165. {
  166.     bitstring rhs(b);
  167.  
  168.     equalize(rhs);
  169.     for (int i = 0; i < nblks_; ++i)
  170.         bits_[i] |= rhs.bits_[i];
  171.     cleanup();
  172.     return *this;
  173. }
  174.  
  175. bitstring& bitstring::operator^=(const bitstring& b)
  176. {
  177.     bitstring rhs(b);
  178.  
  179.     equalize(rhs);
  180.     for (int i = 0; i < nblks_; ++i)
  181.         bits_[i] ^= rhs.bits_[i];
  182.     cleanup();
  183.     return *this;
  184. }
  185.  
  186. bitstring& bitstring::operator>>=(size_t n)
  187. {
  188.     if (n >= nbits_)
  189.         reset();
  190.     else
  191.     {
  192.         for (int i = nbits_ - 1; i >= n; --i)
  193.             (void) set_(i,test_(i-n));
  194.         for (i = 0; i < n; ++i)
  195.             reset_(i);
  196.     }
  197.     return *this;
  198. }
  199.  
  200. bitstring& bitstring::operator<<=(size_t n)
  201. {
  202.     if (n >= nbits_)
  203.         reset();
  204.     else
  205.     {
  206.         for (int i = 0; i < nbits_ - n; ++i)
  207.             (void) set_(i,test_(i+n));
  208.         for (i = nbits_ - n; i < nbits_; ++i)
  209.             reset_(i);
  210.     }
  211.     return *this;
  212. }
  213.  
  214. bitstring& bitstring::operator+=(const bitstring& b)
  215. {
  216.     assert(nbits_ + b.nbits_ < NPOS);
  217.     int oldlen = nbits_;
  218.  
  219.     length(nbits_ + b.nbits_);
  220.     for (int i = 0; i < b.nbits_; ++i)
  221.         (void) set_(oldlen+i,b.test_(i));
  222.  
  223.     return *this;
  224. }
  225.  
  226. bitstring& bitstring::insert(size_t pos, const bitstring& b)
  227. {
  228.     assert(pos <= nbits_);
  229.     size_t oldlen = nbits_;
  230.     size_t newlen = nbits_ + b.nbits_;
  231.  
  232.     // Grow to accommodate insertion
  233.     length(newlen);
  234.  
  235.     // Move tail to right
  236.     for (int i = 0; i < oldlen - pos; ++i)
  237.         set_(newlen-i-1,test_(oldlen-i-1));
  238.  
  239.     // Replicate b in between
  240.     for (i = 0; i < b.nbits_; ++i)
  241.         set_(pos+i,b.test_(i));
  242.  
  243.     return *this;
  244. }
  245.  
  246. bitstring& bitstring::remove(size_t pos, size_t n)
  247. {
  248.     assert(pos < nbits_);
  249.  
  250.     if (n > nbits_ - pos)
  251.         n = nbits_ - pos;
  252.  
  253.     // Slide tail down to cover gap
  254.     for (int i = 0; i < nbits_ - pos - n; ++i)
  255.         set_(pos+i,test_(pos+n+i));
  256.  
  257.     // Shrink
  258.     length(nbits_ - n);
  259.     return *this;
  260. }
  261.  
  262. bitstring& bitstring::replace(size_t pos, size_t n, const
  263. bitstring& b)
  264. {
  265.     assert(pos <= nbits_);
  266.     if (n > nbits_ - pos)
  267.         n = nbits_ - pos;
  268.  
  269.     size_t oldlen = nbits_;
  270.     size_t newlen = oldlen - n + b.nbits_;
  271.     int diff = newlen - oldlen;
  272.  
  273.     // Adjust length and move tail as needed
  274.     if (diff > 0)
  275.     {
  276.         // Grow
  277.         length(newlen);
  278.         for (int i = oldlen - 1; i >= pos + n; --i)
  279.             (void) set_(i+diff,test_(i));
  280.     }
  281.     else if (diff < 0)
  282.     {
  283.         // Shrink
  284.         for (int i = pos + n; i < oldlen; ++i)
  285.             (void) set_(i+diff,test_(i));
  286.         length(newlen);
  287.     }
  288.  
  289.     // Copy b into place
  290.     for (int i = 0; i < b.nbits_; ++i)
  291.         (void) set_(pos+i,b.test_(i));
  292.  
  293.     return *this;
  294. }
  295.  
  296. size_t bitstring::find(int val, size_t pos) const
  297. {
  298.     assert(pos < nbits_);
  299.  
  300.     for (size_t i = pos; i < nbits_; ++i)
  301.     {
  302.         int t = test_(i);
  303.         if (val && t || !val && !t)
  304.             return i;
  305.     }
  306.     return NPOS;
  307. }
  308.  
  309. size_t bitstring::rfind(int val, size_t pos) const
  310. {
  311.     assert(pos < nbits_);
  312.  
  313.     for (int i = pos; i >= 0; --i)
  314.     {
  315.         int t = test_(i);
  316.         if (val && t || !val && !t)
  317.             return i;
  318.     }
  319.     return NPOS;
  320. }
  321.  
  322. bitstring bitstring::substr(size_t pos, size_t n) const
  323. {
  324.     assert(pos <= nbits_);
  325.     if (n > nbits_ - pos)
  326.         n = nbits_ - pos;
  327.  
  328.     bitstring b(0,n);
  329.     for (int i = 0; i < n; ++i)
  330.         b.set_(i,test_(pos + i));
  331.     return b;
  332. }
  333.  
  334. size_t bitstring::length(size_t n, int val)
  335. {
  336.     size_t oldlen = nbits_;
  337.     size_t nw1 = nblks_;
  338.     size_t nw2 = nblks(n);
  339.  
  340.     // Alter the size of a bitstring
  341.     if (nw1 != nw2)
  342.     {
  343.         Block *newbits = new Block[nw2];
  344.         for (int i = 0; i < nw1 && i < nw2; ++i)
  345.             newbits[i] = bits_[i];
  346.  
  347.         delete [] bits_;
  348.         bits_ = newbits;
  349.  
  350.         for (i = nw1; i < nw2; ++i)
  351.             bits_[i] = val ? ~Block(0) : Block(0);
  352.         nblks_ = nw2;
  353.     }
  354.  
  355.     nbits_ = n;
  356.     make_clean_mask();
  357.     cleanup();
  358.     return oldlen;
  359. }
  360.  
  361. size_t bitstring::trim()
  362. {
  363.     for (int i = nbits_ - 1; i >= 0; --i)
  364.         if (test_(i))
  365.             break;
  366.     size_t newlen = i + 1;
  367.     length(newlen);
  368.     return newlen;
  369. }
  370.  
  371. ostream& operator<<(ostream& os, const bitstring& b)
  372. {
  373.     os << b.to_string();
  374.     return os;
  375. }
  376.  
  377. istream& operator>>(istream& is, bitstring& b)
  378. {
  379.     const size_t N = 256;
  380.     char *buf = new char[N];
  381.     char c;
  382.  
  383.     // Consume bit characters
  384.     is >> ws;
  385.     for (int i = 0; i < N && is.get(c); ++i)
  386.     {
  387.         if (c == '0' || c == '1')
  388.             buf[i] = c;
  389.         else
  390.         {
  391.             is.putback(c);
  392.             break;
  393.         }
  394.     }
  395.     buf[i] = '\0';
  396.  
  397.     if (i == 0)
  398.         is.clear(ios::failbit);
  399.     else
  400.     {
  401.         delete [] b.bits_;
  402.         b.from_string(string(buf));
  403.     }
  404.  
  405.     delete buf;
  406.     return is;
  407. }
  408.  
  409. // Private Functions:
  410. int bitstring::set_(size_t n, int val)
  411. {
  412.     if (val)
  413.         set_(n);
  414.     else
  415.         reset_(n);
  416.     return !!val;
  417. }
  418.  
  419. void bitstring::from_string(const string& s)
  420. {
  421.     // Assumes string contains only 0's and 1's
  422.     init(s.length());
  423.     for (int i = 0; i < s.length(); ++i)
  424.         if (s.get_at(i) == '1')
  425.             set_(i);
  426. }
  427.  
  428. void bitstring::init(size_t n)
  429. {
  430.     nbits_ = n;
  431.     nblks_ = nblks(n);
  432.     if (n > 0)
  433.         bits_ = new Block[nblks_];
  434.     else
  435.         bits_ = 0;
  436.     memset(bits_,0,nblks_ * sizeof bits_[0]);
  437.     make_clean_mask();
  438. }
  439.  
  440. void bitstring::equalize(bitstring& b)
  441. {
  442.     // Make the smaller the size of the larger
  443.     if (b.nbits_ < nbits_)
  444.         b.length(nbits_);
  445.     else if (nbits_ < b.nbits_)
  446.         length(b.nbits_);
  447. }
  448.